\chapter{遗传算法}
如果说模拟退火法是物理规律给计算机模拟带来的启示，那么遗传算法的启发来
自生物的进化过程。从宏观角度看，达尔文的进化论解释了生物种群的进化；而
从微观角度，DNA等遗传物质的发现又为进化论提供了良好的理论和物质基础。
而具体表现就是在自然界，当生物种群面对环境的挑战时，可以通过进化改变种
群以更好的适应环境。早期的机器学习研究人员注意到了这个现象，并将其引入
计算机模拟，在John Holland 1975年出版的专著 Adaptation in Natural and
Artificial Systems\cite{Holland1975} 中，这一类算法被称遗传算法（Genetic Algorithms）。

本质上说，Holland创建的遗传算法是一种概率搜索算法（就像Monte Carlo法一
  样）。它将可行解用某种编码对应为固定长度二进制数串（称为染色体，
  chromosome，有时也称作DNA），然后同时关注一个固定数量的可行解（称为
  种群，population）。算法计算每个可行解的目标函数值（称为适应度），然
后根据适应度的分布从种群中随机抽取优势个体复制到下一代（优胜劣汰）。在
复制过程中，有一定概率发生染色体交叉以及变异，从而对种群引入新的个体。
以上原理都来源于对生物进化和生物有性生殖遗传过程的模拟。在若干代复制后，
算法期待种群的整体适应度能有所提高，并且在一定条件下，优势个体能逼近全
局最优解。

接下去我们先用一个简单的例子来说明遗传算法的具体流程。

\section{遗传算法描述}
假设我们有四家连锁快餐店，现在我们要作出以下三个决策：
\begin{itemize}
\item 汉堡的价格，两个选项：0.5美元或1美元；
\item 饮料的策略，供应酒还是供应可乐；
\item 服务方式，自助还是点单。
\end{itemize}

现在我们有三个决策变量，每个变量可能为两个值中的一个（非常简化了），也
即可以用一个比特（一位二进制）来表示。这样我们能用一个3位二进制串来表
达一个可行解，也即串的长度$l = 3$。而每个位只有$0$和$1$两种状态，也即
染色体规模是$k = 2$。事实上对这个问题，整个解空间只有$8$个可行解，而每
个解都有唯一确定的染色体表示。现在我们随便取$N = 4$个可行解构成我们的
种群，$N$表示种群中个体数量：

\begin{center}
%  \centering
  \begin{tabular}[!p]{ccccc}
\hline
编号 & 价格 & 饮料  & 服务 & 染色体\\
\hline
1 & 高 & 可乐 & 自助 & 011 \\
\hline
2 & 高 & 酒 & 自助 & 001 \\
\hline
3 & 低 & 可乐 & 点餐 & 110 \\
\hline
4 & 低 & 可乐 & 点餐 & 010 \\
\hline
\end{tabular}
%  \caption{快餐店的决策}
%  \label{table::instent_food_store}
\end{center}

接下去我们要计算每个个体的适应值，也即目标函数值。在这里，可以认为是每
一种方案的利率。通常的做法是首先要将每一个染色体串解码成有意义的可行解，
然后计算每个可行解对应的目标函数值。在这里，为了简化，我们就直接把染色
体串对应的十进制数作为适应值。我们的目标仍然是求适应值的最大。对以上初
始种群，我们有以下的适应值：

\begin{center}
%  \centering
  \begin{tabular}[!ht]{ccc}
\hline
编号 & 染色体 & 适应值\\
\hline
1 & 011 & 3 \\
\hline
2 & 001 & 1 \\
\hline
3 & 110 & 6\\
\hline
4 & 010 & 2\\
\hline
\end{tabular}
%  \caption{快餐店决策的适应值}
%  \label{table::fe_instent_food_store}
\end{center}

其中，平均适应值是$3.0$，最大适应值是$6.0$。现在我们考虑如何产生第二代
种群。首先我们保持种群数量不变，也就是第二代仍然要有4个个体，而它们大
部分要从第一代复制下来。我们希望从第一代择优复制到第二代，但同时又能保
持一定的随机性，于是一个合理的策略是根据每个个体的表现值和总表现值之比
作为概率密度，也即抽取到第$i$个个体$x_i$的概率是
\begin{equation}
  P\{X = x_i\} = p_i = \frac{f_i}{\sum_{k = 1}^N f_k}.
  \label{eq::gene_sample}
\end{equation}
在随机优化领域，这种抽取方式被称作轮盘赌（roulette）。在实际操作中，可
以用我们第一章学过的直接抽取方式进行抽取。之所以要保持随机性是因为我们
的种群并不是退化的，也就是它有可能会产生新的个体，而当前表现恶劣的解，
它的后代未必就一定恶劣，因此也应该有一定的概率，让它能产生后代，以保持
种群整体的丰富。同时我们也注意到，直接的复制是不会带来任何新的改变的，
因此我们还要引入启迪于两性生殖遗传的新算子。

两性生殖中一个关键现象是杂交（crossover）。子代会同时具有双亲的一部分特征。这一点的
模拟通过染色体的交叉完成。当然首先我们要从上一代中，抽取（以下若不加说
  明，抽取都是指轮盘赌抽取）两个双亲个体，比如：$x_1 = 011$和$x_2 =
110$。然后我们要在$1 \~ l - 1$之间随机选取一个整数，称为交叉点，比如$i
= 2$。然后产生新个体
$$
x_1' = x_{11}x_{12}\cdots x_{1i}x_{2,i+1}x_{2,i+2}\cdots x_{2l}.
$$
和
$$
x_2' = x_{21}x_{22}\cdots x_{2i}x_{1,i+1}x_{1,i+2}\cdots x_{1l}.
$$
放入新一代。比如这里，$x_1' = 010$，$x_2' = 111$（注意$x_2'$实际是全
  局最优解）。整个杂交过程可表示为：
$$
\begin{array}{l}
  01|1\\
  11|0
\end{array}
\to
\begin{array}{l}
  010\\
  111
\end{array}.
$$

杂交不但引入新个体，而且保留了上一代个体的染色体片段，若两个染色体中同
时具有相同的片段，那么在杂交操作中很可能可以得到保留。因此交叉的意义除
了引入新个体，还有一个更重要的目的是在染色体片段，也就是基因层面上进行
择优。

光靠杂交引入新个体是不够的，特别是在基因层面上，更新更慢。所以再次仿照
自然界的规律，我们引入突变（mutation）算子。具体说，从上一代抽取一个个
体$x$，然后随机选择一个$1 \sim l$的整数$i$，将$x$的第$i$位$x_i$取反，也即
$$
x_i = \left\{
\begin{array}{ll}
  0,& \mbox{若} x_i = 1; \\
  1,& \mbox{其他}.
\end{array}
\right.
$$
然后将$x$放入新一代。突变的作用主要是要弥补因优胜劣汰造成的种群退化，
维持种群基因的丰富性。

在一般的遗传算法中，在每一代的复制过程中，我们都要决定三个参数$p_r$，
$p_c$和$p_m$都大于$0$，且满足
$$
p_r + p_c + p_m = 1. 
$$
分别表示一次抽取以后，发生复制、交叉和突变的概率。

而遗传算法的整体设计思路，包括一下四个步骤：
\begin{enumerate}
\item 确定编码方案；
\item 确定目标函数以及和适应度之间的转换；
\item 确定控制算法的参数，除了上面的$p_r$，$p_c$和$p_m$，一般还有种群数量$N$；
\item 确定终止策略。
\end{enumerate}

终止策略在实际计算中有很多可以选择的方式。比如直接复制一个有限的代数；
或者观察到平均适应值达到一个预置的优化目标；再或者发现种群退化严重，等
等。

遗传算法的适用范围很广。比如对于连续优化问题
$$
\begin{array}{ll}
  \min & f(x) \\
  \mbox{s. t.}& x \in D.
\end{array}
$$
我们可以将$D$剖分成很小的区域再用二进制表示作为染色体。而目标函数本
身就可以作为适应值函数。

\section{遗传算法的数学基础}

我们用$A(t)$表示第$t$代的种群，而其中一个个体用$A_j$，$j = 1, 2,
\cdots, n$表示。不失一般性，对一个单独的个体$A_j$，规定染色体为$l$位二
进制，并用$a_i$表示，$i = 1, 2, \cdots, l$，且$a_i$非$0$即$1$。即
$$
A_j = a_1a_2\cdots a_l.
$$
这里$n$表示种群中的个体总数。

为了对应基因，我们引入模式（Schema）的概念。一个模式是由由$0$，$1$和
$*$构成长度为$l$的串，其中$0$和$1$表示确定的位，而$*$表示可以随意取$0$
或$1$的位。比如，对$l = 7$的模式$H = *11*0**$，实际上代表了集合
$$
\{0110000, 1110000, 0111000, 0110010, 0110001, 1111000, 1110010, 1110001, \cdots\}
$$
共$16$个染色体集合。如果$A \in H$，则称$A$和$H$匹配。

一般地，长度为$l$的串，可能的模式共有$3^l$个。若符号个数$k > 2$，则可
能的模式共有$(k + 1)^l$个。而一个种群中，至多包含了$n2^l$个可能的模式。

模式有两个重要概念：阶和定义长度。

\begin{definition}{\hei 阶和定义长度}
模式的阶指模式中确定位的个数，记作$o(H)$。比如：
$$
o(011*1**) = 4.
$$
而模式的第一个确定位和最后一个确定位之间的距离称为定义长度，记作$\delta(H)$。比如：
$$
\delta(011*1**) = 5 - 1 = 4, \delta(*0*****) = 0.
$$
\end{definition}

如果对给定模式$H$，第$t$代种群$A(t)$中有$m$个个体和$H$匹配，则记作$m =
m(H, t)$。现在考虑各个算子对模式的影响。首先是复制。前面已经说过，一个
个体$A_i$在下一代被抽到的概率是
$$
p_i = \frac{f_i}{\sum_{j = 1}^n f_j}.
$$
现在令
$$
\bar{f}(t) = \frac{\sum_{j = 1}^n f_j}{n}
$$
表示一个种群在第$t$代的平均适应度。不妨设符合模式$H$的个体集合为$\{A_k,k\in \Lambda\}$（这里$\Lambda$为一指标集），则模式的平局适应度由
\[
f(H,t)=\frac{1}{m(H,t)}\sum_k f_k
\]
给出，于是有
\begin{eqnarray*}
  E[m(H, t + 1)] & = & n\cdot P\{\text{符合模式$H$的个体在$t+1$代被抽到}\}\\
  & = & n\cdot\sum_k \frac{f_k}{\sum_{j=1}^n f_j}\\
  & = & \frac{1}{\bar{f}(t)}\sum_k f_k\\
  & = & \frac{1}{\bar{f}(t)}m(H,t)f(H,t)\\
  & = & m(H, t) \frac{f(H,t)}{\bar{f}(t)}.
\end{eqnarray*}
也即一个模式在从$t$代到$t+1$代的复制操作中的增长率是这个模式的平均适应度比上整个种群的平均适应度。当种群数量足够大时$E[m(H,t+1)]$与$m(H,t+1)$可近似相等，接下来假设该条件成立，考虑$m(H,t+1)$.现在假设种群中有一个模式，它的平均适应度是$(1 + c)\bar{f}(t)$，
也即比种群整体平均适应度高出一个常数因子$c$，则有
$$
m(H, t + 1) = m(H, t) \frac{(1+c)\bar{f}(t)}{\bar{f}(t)} = (1 + c)m(H, t).
$$
假设从$t = 0$起，$c$就是一个常数，那么到第$t$代，有
$$
m(H, t) = m(H, 0)(1 + c)^t.
$$
这个结果告诉我们，一个高于平均适应度的模式，在种群中在复制的作用下以
指数增长。但注意这里实际上有多个模式并行地存在，同时$\bar{f}$也在不断
地改变，所以实际过程会更加复杂。但复制操作保证了优势基因的数量增长这一
点仍然成立。

接着我们考虑杂交算子对不同模式的影响。我们看两个阶都是$2$的模式：$H_1
= *1****0$和$H_2 = ***10**$。他们一个共同的实例是$A = 0111000$。现在假
设$A$被选中作为杂交操作的对象之一。那么杂交位置$c$落在$1 \sim 7$是等概的，
但只有$c = 4$一个可能才会破坏$H_2$的模式，然而$c = 2, 3, 4, 5, 6$共$5$
个位置都会破坏模式$H_1$。显然，一个模式$H$能继续存在的概率是
\begin{equation}
  p_S = 1 - \frac{\delta(H)}{l - 1},
  \label{eq::GA_ps}
\end{equation}
而在两代之间，为了便于分析，我们稍微调整一下我们的策略，我们先完整地用
复制操作复制整个种群，然后用杂交算子以概率$p_c$替换其中部分子代个体。
这样可以有
\begin{equation}
  m(H, t + 1) = m(H, t) \frac{f(H)}{\bar{f}}\left[1 - p_c
    \frac{\delta(H)}{l - 1}\right].
\end{equation}
现在我们来看复制和杂交两个算子对特定模式数量的影响。主要依赖两个因素：
这个模式的平均适应度是在种群平均适应度$\bar{f}$之上还是之下；以及这个
模式的定义长度和染色体长度的比值。

最后考虑变异算子，假设以概率$p_m$发生变异。由于变异是对模式中的确定位而言的，故一旦发生变异该模式无法存活，从而对一个阶为$o(H)$的模式而言，其存活概率为$(1-p_m)^{o(H)}$. 注意到当$p_m<<1$时有
$$
(1 - p_m)^{o(H)} \approx 1 - p_m o(H).
$$
此外，由于在交叉和变异过程中不仅会破坏模式，也有可能产生新的符合模式的个体，所以总体上看，复制、交叉和变异三个算子对一个特定模式的综合作用，可以表示为：
\begin{equation}
  m(H, t + 1) \geq m(H, t)\frac{f(H)}{\bar{f}}
  \left[1 - p_c\frac{\delta(H)}{l - 1} - p_mo(H)\right].
  \label{eq::GA_model}
\end{equation}

综合上述理解，我们先给出一个遗传算法中的重要结论——模式定理：

\begin{theorem}
  具有短定义长度、低阶并且平均适应度高于整体平均适应度的模式在遗传算法迭代
  过程中以指数增长率被采样。
\end{theorem}

这个定理告诉我们，并不是所有模式，都在遗传算法中“活跃”。在串长为
$l$，规模为$n$的二进制串种群中，可能的模式个数在$2^l \sim n2^l$之间，而
其中低阶，短定义长度的模式数量大概在$O(n^3)$级别。也就是说，遗传算法是
隐含地并行搜索这么多种模式的搭配情况。这一点被 Holland 称为遗传算法的
隐含并行性。但它既是遗传算法的一个优势，同时也是局限所在。由于低阶、短
定义长度和高适应值的模式的重要性，在遗传算法中，被称为基因块（gene
  block）。于是就有假设：基因块是否总能组成适应值更高的串？这一假设被
称为基因块假设。

对于某个具体的问题，我们可以用划分系数变换来求模式的平均适应值，并进一
步检测基因块假设是否成立。将染色体到适应值看作是$l$位串到$\mathbb{R}$的映射$f$：
$$
f : \{0, 1\}^l \to \mathbb{R}.
$$
我们定义划分数$j$如下：
\begin{equation}
  j(H) = \sum_{i = 0}^{l - 1}\alpha(b_i)2^i,
  \label{eq::GA_split}
\end{equation}
其中，$b_i$是从串在第$i$位的值（这里计数次序是最右为第$0$位，最左为第
  $l - 1$位），函数$\alpha$为
\begin{equation}
  \alpha(b) = \left\{
  \begin{array}{ll}
    0, &\mbox{若}b = *,\\
    1, &\mbox{其它}.
  \end{array}
  \right.
  \label{eq::GA_bit_mark}
\end{equation}
如果将一个确定位和一个$*$位的变化看作一个划分，那么一个长度为$l$的串可
以有$2^l$种划分，而划分数函数给每一种划分一个唯一的值。比如：
$$
j(***) = 0, j(**0) = j(**1) = 1, j(0*1) = 5.
$$
（其实就是对应一个二进制数）

继续定义
\begin{equation}
  \sigma(H) = \prod_{i = 0}^{l - 1}(-1)^{\beta(b_i)}
  \label{eq::GA_bit_filter}
\end{equation}
其中，
\begin{equation}
  \beta(b) = \left\{
  \begin{array}{ll}
    1, &\mbox{若}b = 0,\\
    0, &\mbox{其它}.
  \end{array}
  \right.
  \label{eq::GA_bit_mark}
\end{equation}
以及划分系数变换：
\begin{equation}
  f(H) = \sum_{H' \supseteq H} \sigma(H')\epsilon_j(H').
  \label{eq::GA_split_eq}
\end{equation}
这里$\epsilon_j$称为划分系数，如果将$f(H)$看做是已知，那么变换
（\ref{eq::GA_split_eq}）就代表一个关于$\epsilon_j$的方程。这样的方程
一共有$3^l$个（一个潜在的模式一个），但划分系数只有$2^l$个，所以只要写
出$2^l$个就能求出来了。

\begin{example}
  令$f(x) = x^2$，将$x$用$3$位二进制整数表示（$0 \sim 7$）。我们只考虑含
  $1$和$*$的模式，则有
  \begin{eqnarray*}
    f(***) & = & \epsilon_0\\
    f(**1) & = & \epsilon_0 + \epsilon_1 \\
    f(*1*) & = & \epsilon_0 + \epsilon_2 \\
    f(*11) & = & \epsilon_0 + \epsilon_1 + \epsilon_2 + \epsilon_3 \\
    f(1**) & = & \epsilon_0 + \epsilon_4\\
    f(1*1) & = & \epsilon_0 + \epsilon_1 + \epsilon_4 + \epsilon_5\\
    f(11*) & = & \epsilon_0 + \epsilon_2 + \epsilon_4 + \epsilon_6\\
    f(111) & = & \epsilon_0 + \epsilon_1 + \epsilon_2 + \epsilon_3 + \epsilon_4 + \epsilon_5 + \epsilon_6 + \epsilon_7
  \end{eqnarray*}

这里$f(***), f(**1), \cdots, f(111)$等模式的值可直接计算得到。求解上述
方程得到$\epsilon_0, \cdots, \epsilon_7$，然后我们可以直接计算其他模式
的平均适应值，比如$f(**0) = \epsilon_0 - \epsilon_1$。
\end{example}

划分系数是分析遗传算法中诸模式动态的一个工具。比如，我们可以考虑两个模
式$H_1 = **1$和$H_2=**0$的竞争关系：
\begin{eqnarray*}
  f(**1) & = & \epsilon_0 + \epsilon_1\\
  f(**0) & = & \epsilon_0 - \epsilon_1.
\end{eqnarray*}
可以直观地看到那一种模式结构影响了这两种模式的竞争关系。另一个自然的想
法是高阶模式是否可以由低阶模式拼装？比如模式$*11$是否可以由$*1*$和
$**1$拼装出来？我们可以看到，后两者的划分系数中缺少了前者所拥有的
$\epsilon_3$。

基于上述的认识，我们可以先直观第讨论一下简单遗传算法，即只包含复制、交
叉（单点交叉）和变异（单点）三个算子，且采用轮盘赌策略抽取的遗传算法。
显然，如果有下面两个情况同时发生：
\begin{enumerate}
  \item 最优解具有高阶、长定义长度的模式；（违背基因块假设）
  \item 有大量的低阶、短定义长度模式的局部最优解。
\end{enumerate}
那么，遗传算法会收敛到非全局最优解。当然在实际问题中，一个合理设计的算
法可以避免这种情况发生，但无论如何，简单遗传算法缺乏全局收敛性的保证。
